package BTree;

import java.util.LinkedList;
import java.util.Queue;

public class BTree {

    public static class Node{
        char ch;
        Node left;
        Node right;

        public Node(char ch) {
            this.ch = ch;
        }
    }

    public Node creat(){
        Node bNode1=new Node('A');
        Node bNode2=new Node('B');
        Node bNode3=new Node('C');
        Node bNode4=new Node('D');
        Node bNode5=new Node('E');
        Node bNode6=new Node('F');
        Node bNode7=new Node('G');

        bNode1.left=bNode2;
        bNode1.right=bNode3;

     //   bNode2.left=bNode4;
        bNode2.right=bNode5;

        bNode3.left=bNode6;
        bNode3.right=bNode7;

        return bNode1;
    }

public static int size=0;


    // 获取树中节点的个数
    int size(Node root){
     if(root==null){
         return 0;
     }
     return size(root.right)+size(root.right)+1;
    }


    void size1(Node root){
        if(root==null){
            return;
        }
        size++;
        size1(root.right);
        size1(root.left);
    }

    // 获取叶子节点的个数
    public static int leafsize=0;
    void  getLeafNodeCount(Node root){
        if (root==null){
            return;
        }
if(root.right==null&&root.left==null){
    leafsize++;
    return;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
    }

    int getLeafNodeCount1(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount1(root.right)+getLeafNodeCount1(root.left);
    }


// 子问题思路-求叶子结点个数

    // 获取第K层节点的个数
    int getKLevelNodeCount(Node root,int k){
        if(root==null){
            return 0;
        }
       if(k==1&&root!=null){
           return 1;
       }
       return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    // 获取二叉树的高度
    int getHeight(Node root){
     if(root==null){
         return 0;
     }

     int left=getHeight(root.left);
     int right=getHeight(root.right);
     return Math.max(left,right)+1;
    }

    // 检测值为value的元素是否存在
    Node find(Node root, char ch){
        if (root==null){
            return null;
        }
       if(root.ch==ch){
           return root;
       }
    Node left=find(root.left, ch);
       if(left!=null){
           return left;
       }


    Node right=find(root.right, ch);
       if(right!=null){
           return right;
       }
        return null;
    }

    //层序遍历
    void levelOrder(Node root){
        Queue<Node>queue=new LinkedList<>();
if(root!=null){
    queue.add(root);
}
while(!queue.isEmpty()){
    for(int i= queue.size();i>0;i--){
        Node tmp=queue.poll();
        System.out.print(tmp.ch+" ");
        if(tmp.left!=null){
            queue.add(tmp.left);
        }
        if(tmp.right!=null){
            queue.add(tmp.right);
        }
    }
}
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(Node root) {

        if(root==null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
            queue.add(root);
        while (!queue.isEmpty()) {
Node cur=queue.poll();
if(cur!=null){
    queue.add(cur.left);
    queue.add(cur.right);
}else {
    break;
}
        }
        while (!queue.isEmpty()){
            Node cur=queue.poll();
            if(cur!=null){
                return false;
            }
        }
        return true;
    }
}
